package com.example.leetcode;

/**
 * 动态规划 ** 难点 ** 参考题解
 * 最大正方形
 * 右下角 最大边长
 */
public class Demo0221 {
    public static void main(String[] args) {
        char[][] cs=new char[][]{{'1','0','1','0','0','1','1','1','0'},{'1','1','1','0','0','0','0','0','1'},{'0','0','1','1','0','0','0','1','1'},{'0','1','1','0','0','1','0','0','1'},{'1','1','0','1','1','0','0','1','0'},{'0','1','1','1','1','1','1','0','1'},{'1','0','1','1','1','0','0','1','0'},{'1','1','1','0','1','0','0','0','1'},{'0','1','1','1','1','0','0','1','0'},{'1','0','0','1','1','1','0','0','0'}};
        maximalSquare2(cs);
    }
    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n =matrix[0].length;
        int ans[][]=new int[m+1][n+1];
        int res=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]=='1'){
                    ans[i+1][j+1]=Math.min(Math.min(ans[i][j],ans[i][j+1]),ans[i+1][j])+1;
                    res=Math.max(res,ans[i+1][j+1]);
                }
            }
        }
        return res*res;
    }

    public static int maximalSquare2(char[][] matrix) {
        int m = matrix.length;
        int n =matrix[0].length;
        int[][]dp=new int[m+1][n+1];
        int res=0;
        for (int i = 1; i <m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                //1.边界条件为0时不考虑
                if (matrix[i-1][j-1]=='1'){
                    int temp=Math.min(dp[i-1][j],dp[i][j-1]);
                    if ((i-temp-1 >=0 && j-temp-1>=0) && matrix[i-temp-1][j-temp-1]=='1'){
                        dp[i][j]=temp+1;
                    }else {
                        dp[i][j]=temp;
                    }
                    res=Math.max(res,dp[i][j]);
                }
            }
        }
        return res*res;
    }
}
